const { ListNode, LinkedList } = require('../2. 链表/1. 链表基础/1. 建立线性链表.js')

// 给定链表头节点head，返回链表的中间节点，如果有两个中间节点，则返回第二个中间节点
// 思路1，先遍历一遍链表，统计节点个数n，然后再遍历到n / 2的位置，返回中间位置

function middleNode(head) {
    let len = 0
    let cur = head
    while (cur) {
        len++
        cur = cur.next
    }
    let mid = Math.floor(len / 2)
    cur = head
    while (mid--) {
        cur = cur.next
    }
    return cur
}

let list = new LinkedList([2, 5, 1, 7, 3, 9])
console.log(middleNode(list.head))

// 思路2，快慢指针
// slow和fast指针指向链条头节点，slow每次移动一步，fast每次移动两步，fast需要判断fast和fast.next才能进入下次循环
function middleNode2(head) {
    let slow = head
    let fast = head
    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
}

let list2 = new LinkedList([2, 5, 1, 7, 3, 9])
console.log(middleNode2(list2.head))